Ugly number III [Inclusion-Exclusion Principle]

Time: O(LogN); Space: O(1); medium

Write a program to find the n-th ugly number.

Ugly numbers are positive integers which are divisible by a or b or c.

Example 1:

Input: n = 3, a = 2, b = 3, c = 5

Output: 4

Explanation:

  • The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10… The 3rd is 4.

Example 2:

Input: n = 4, a = 2, b = 3, c = 4

Output: 6

Explanation:

  • The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12… The 4th is 6.

Example 3:

Input: n = 5, a = 2, b = 11, c = 13

Output: 10

Explanation:

  • The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13… The 5th is 10.

Example 4:

Input: n = 1000000000, a = 2, b = 217983653, c = 336916467

Output: 1999999984

Constraints:

  • 1 <= n, a, b, c <= 10^9

  • 1 <= a * b * c <= 10^18

  • It’s guaranteed that the result will be in range [1, 2 * 10^9]

Hints:

  1. Write a function f(k) to determine how many ugly numbers smaller than k. As f(k) is non-decreasing, try binary search.

  2. Find all ugly numbers in [1, LCM(a, b, c)] (LCM is Least Common Multiple). Use inclusion-exclusion principle to expand the result.

1. Binary Search [O(LogN), O(1)]

[1]:

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
    def nthUglyNumber(self, n, a, b, c):
        """
        :type n: int
        :type a: int
        :type b: int
        :type c: int
        :rtype: int
        """
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a

        def lcm(x, y):
            return x//gcd(x, y)*y

        def count(x, a, b, c, lcm_a_b, lcm_b_c, lcm_c_a, lcm_a_b_c):
            return x//a + x//b + x//c - (x//lcm_a_b + x//lcm_b_c + x//lcm_c_a) + x//lcm_a_b_c

        lcm_a_b, lcm_b_c, lcm_c_a = lcm(a, b), lcm(b, c), lcm(c, a)
        lcm_a_b_c = lcm(lcm_a_b, lcm_b_c)

        left, right = 1, 2*10**9

        while left <= right:
            mid = left + (right-left) // 2
            if count(mid, a, b, c, lcm_a_b, lcm_b_c, lcm_c_a, lcm_a_b_c) >= n:
                right = mid - 1
            else:
                left = mid + 1

        return left

[2]:

s = Solution1()

n = 3
a = 2
b = 3
c = 5
assert s.nthUglyNumber(n, a, b, c) == 4

n = 4
a = 2
b = 3
c = 4
assert s.nthUglyNumber(n, a, b, c) == 6

n = 5
a = 2
b = 11
c = 13
assert s.nthUglyNumber(n, a, b, c) == 10

n = 1000000000
a = 2
b = 217983653
c = 336916467
assert s.nthUglyNumber(n, a, b, c) == 1999999984